Приложения конструктивных описаний графов
При использовании конструктивного подхода для решения задач на
графах в качестве исходных выбираются максимальные по включению
графы, для которых рассматриваемая задача решается наиболее эффективно.
Далее из них строится суперпозиция, реализующая заданный граф. Анализ
структура графа упрощается, если строить его «по кирпичику», когда, по
крайней мере, один из графов-операндов каждой операции склейки
принадлежит множеству исходных графов, т.е. если пользоваться
каноническими суперпозициями. В качестве примера далее рассматриваются
задачи оптимального размещения информации (графов).
Решение широкого круга прикладных задач связано с размещением
объектов той или иной природы в элементах определенных структур.
Необходимость в подобных задачах возникает, например, при расположении
данных в памяти ЭВМ, расстановке оборудования в цехах, размещении
электронных схем на платах и т.д.
Размещаемые объекты обладают, как правило, определенной
совокупностью взаимосвязей, задаваемых соответствующим графом. Задача
состоит в поиске такого размещения вершин графа, при котором достигался
бы экстремум некоторого функционала, характеризующего свойства
размещения.
Решение задач размещения графов требует в общем случае проведения
перебора большого числа вариантов. Ограничимся здесь случаем линейного
размещения, когда вершины графов располагаются в заданных позициях
вдоль прямой. Выберем в качестве таковых целочисленные точки прямой.
При этом задачу можно сформулировать как задачу нумерации вершин графа
натуральными числами.
1.Свойства минимальных нумераций
Пусть G(V,E) граф, содержащий n вершин; A={a
1
, a
2
,..., a
n
}, a
i
< a
i+1
,
i=1,2,…,n-1 - множество из n натуральных чисел. Взаимнооднозначное
отображение
: V(G)
A называется нумерацией вершин графа G